#include <functional>
#include <iostream>
#include <vector>
void backtrace(const std::vector<int> &set, std::vector<int> &choices,
               std::vector<std::vector<int>> &res, int start, int target) {
  for (int i = start; i < set.size(); i++) {
    if (target - set[i] == 0) {
      // 避免相同元素重复选择
      if (i == 0 || set[i] != set[i - 1]) {
        choices.push_back(set[i]);
        res.push_back(choices);
        // 回退
        choices.pop_back();
      }
    }
    if (target - set[i] < 0) {
      return;
    }
    if (target - set[i] > 0) {
      if (i == 0 || set[i] != set[i - 1]) {
        target -= set[i];
        choices.push_back(set[i]);
        backtrace(set, choices, res, i + 1, target);
        // 回退
        choices.pop_back();
        target += set[i];
      }
    }
  }
}

std::vector<std::vector<int>> subSetNum(std::vector<int> set, int target) {
  std::vector<std::vector<int>> res;
  std::vector<int> choices;
  std::sort(set.begin(), set.end(), std::less<int>());
  backtrace(set, choices, res, 0, target);
  return res;
}

int main() {
  std::vector<int> set{3, 4, 5, 4, 2, 3, 1, 5};
  int target{9};
  auto res = subSetNum(set, target);
  for (auto &s : res) {
    for (auto i : s) {
      std::cout << i << " ";
    }
    std::cout << std::endl;
  }
  return 0;
}